As used herein "f(x)", refers to a general class of n dimensional signals or value measurements (e.g. light intensity, voltage level, temperature, height, weight, etc.) where x=(x.sub.1, . . . x.sub.n) is a vector in n dimensional space. Although applicable to arbitrary values of n, the following discussion assumes n=2 for ease of illustration and comprehension. In this simpler context, f(x) is a function defined over the usual (x,y) plane, and f is referred to as an image, even in the case where x and y take continuous (non-discrete) values. Thus, x refers to some location in an image. In the discretized case, x refers to a particular pixel in a real image.
In addition, "g(y)" refers to a class, generally preestablished, of n dimensional values where y=(y.sub.1, . . . y.sub.n) is a vector in n dimensional space. In particular, g(y) serves as a standard against which f(x) is measured for purposes of image processing, and especially pattern matching as discussed next.
A large class of image processing operations involve moving a "kernel" g (variously called a window, template, or stencil) over an image f and performing an operation on the pairs of points that are superimposed at each relative displacement of f and g. This is illustrated in FIG. 1, where the point in f being probed is x. The kernel is positioned over the image such that the kernel origin (or reference point) coincides with x. Each point y of g, is defined with respect to the kernel origin. The set of points over which g is defined is denoted by Ros(g), i.e. region of support of g. Note that Ros(g) may be a rectangle as shown in FIG. 1 or the set of points defining a more complex shape (as shown in FIG. 2). In FIG. 1 it is clearly seen that a kernel point y coincides with the image point x+y. Consequently, the pairs of values to be considered at each point y .epsilon. Ros(g) are f(x+y) and g(y).
This common framework is employed by three traditional shape matching techniques: template matching by cross correlation, function mathematical morphology (MM) dilation, and function MM erosion. In each case, the value of g have the same dimensionality as the values of f (e.g., f and g may both have units of temperature, range, etc.). In the following equations, .sym. and .crclbar. are the symbols for Minkowski addition and Minkowski subtraction, respectively. The symbol g indicates the symmetric function of g, i.e., g(x)=g(-x).
In cross correlation, the values f(x+y) and g(y) considered at each kernel point y .epsilon. Ros(g) are multiplied, and the sum (or integral) of the f and g value pair products defines the final outcome of the template matching. Restated as an equation, cross correlation matching, i.e. cc(x), is defined as follows: ##EQU1##
In function MM dilation, the values f(y+y) and g(y) considered at each kernel point y .epsilon. Ros(g) are summed together, and the maximum f and g value pair sum defines the final outcome of the template matching. Expressed as an equation, function MM dilation matching, i.e. md(x), is defined as follows: EQU md(x)=[f.sym.g](x)=MAX.sub.y {f(+y)+g(y)}, y.epsilon.Ros(g). Equation 2
In function MM erosion, the difference of the values f(x+y) and g(y) considered at each kernel point y .epsilon. Ros(g is computed, and the minimum f and g value pair difference is used as the final outcome of the template matching. The equation defining function MM erosion, i.e. me(x), reads: EQU me(x)=[f.crclbar.g](x)=MIN.sub.y {f(x+y)-g(y)}, y.epsilon.Ros(g). Equation 3
One disadvantage of template (kernel) matching by cross correlation and MM is that these methods are easily confounded by distortions of shapes within images due to a variety of causes e.g., noise, occlusion (i.e., obscuration), articulation (of shape parts), etc. In the case of noise, methods for reducing noise in images are known but also change those portions of original image data which are noise free. Thus, such image noise reduction methods create a further loss in integrity in image processing.
Despite the lack of robustness, template matching by cross correlation has found application in the recognition of printed characters and the inspection of printed circuit boards (see A. K. Jain, Fundamentals of Digital Image Processing, New Jersey: Prentice-Hall, Inc., 1989, p. 402), and edge detection in medical images. And despite similar limitations, MM is a widely used tool for image processing (see J. Serra, Image Analysis and Mathematical Morphology, New York: Academic Press, 1982).
A further disadvantage of the existing template matching techniques, especially in image processing, is the computational expense in terms of processing time.
Accordingly there is a need for more efficient and robust shape matching apparatus and/or method.